package com.bite;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        int[] arr = {2, 3, 2, 4};
        main.triangleNumber(arr);
    }

    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            if (height[left] < height[right]) {
                max = Math.max(max, height[left] * (right - left));
                left++;
            } else {
                max = Math.max(max, height[right] * (right - left));
                right--;
            }
        }
        return max;
    }

//    public int maxArea(int[] height) {
//        int left = 0, right = height.length - 1, ret = 0;
//        while (left < right) {
//            int v = Math.min(height[left], height[right]) * (right - left);
//            ret = Math.max(ret, v);
//            if (height[left] < height[right]) left++;
//            else right--;
//        }
//            return ret;
//        }

    public int triangleNumber(int[] nums) {
        // 先进行数组排序，从小到大单调排序
//        for(int i=0;i<nums.length;i++){
//            for(int j=i+1;j<nums.length;j++){
//                if(nums[i]>nums[j]){
//                    int temp = nums[i];
//                    nums[i] = nums[j];
//                    nums[j] = temp;
//                }
//            }
//        }
//        Arrays.sort(nums);
//        int left = 0;int right = 0;int c=nums.length-1;int sum = 0;
//        while(c>=2){
//            left =0;
//            right = c-1;
//            while(left<right){
//                if(nums[left]+nums[right]>nums[c]){
//                    sum+=right - left;
//                    right --;
//                }else{
//                    left++;
//                }
//            }
//            c--;
//        }
//        return sum;


        // 击败96.5%
        Arrays.sort(nums);
        int sum = 0;
        int n = nums.length;
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    sum += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return sum;
    }

    public int[] twoSum(int[] price, int target) {
        int n=price.length;
        // 数组是升序排序的
        int left =0;
        int right = n-1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum == target) {return new int[]{price[left], price[right]};}
            else if (sum > target) {right --;}
            else if (sum < target) {left ++;}
        }
        return new int[]{};
    }
}
